\documentclass[a4paper,10pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{longtable}

\usepackage{multicol}
\usepackage{graphicx}
\usepackage{array}
\usepackage{url}
\usepackage[left=2cm,top=3cm,right=2cm,bottom=2cm,head=1.5cm,includefoot]{geometry}
\usepackage{fancyhdr}

%\title{ \textbf{ Trabajo Pr\'actico: Análisis de Algoritmos de Inducción}

%\author{	Zucchiatti, Martín, \textit{85797} \\
%            	\texttt{ tanmartin05@gmail.com } \\[2.5ex]
%		Pereira, María Florencia, \textit{88816} \\
%            	\texttt{mflorenciapereira@gmail.com} \\[2.5ex]
%            	\normalsize{2ndo. Cuatrimestre de 2011} \\
%            	\normalsize{75.70 Sistemas de programación no convencional de Robots} \\
%            	\normalsize{Facultad de Ingenier\'ia, Universidad de Buensos Aires} \\
%       }
%\date{}



\begin{document}
%Caratula
%\maketitle 
%\thispagestyle{empty}

\begin{titlepage}
\thispagestyle{empty}
\begin{center}
\includegraphics[scale=0.3]{./img/logo.jpg}\\
%\large{\textsc{Universidad de Buenos Aires}}\\
\Large Universidad de Buenos Aires\\
\Large{\textsc{Facultad De Ingeniería}}\\
\Large{1\textsuperscript{er} Cuatrimestre 2012}

\vfill

\Huge{\textsc{\textbf{ Trabajo Pr\'actico: 
Análisis de Algoritmos de Inducción}}}

\vfill
\normalsize{\textbf{INTEGRANTES}}\\[3ex]

Zucchiatti, Martín - \textit{85.797} \\
Pereira, María Florencia - \textit{88.816} \\

\vfill
\LARGE{75.70 - Sistemas de programación no convencional de Robots} \\
\end{center}
\end{titlepage}


%Cabecera y pie de pagina
\pagestyle{fancy}
\lfoot{\scriptsize{75.70 Sistemas de programación no convencional de Robots\\
Análisis de Algoritmos de Inducción}}
\cfoot{}
\rfoot{\thepage}

\newpage
\thispagestyle{empty}
\tableofcontents

\newpage
\section{Introducción}
\subsection{Familia TDIDT}
El objetivo de los algoritmos de inducción es encontrar reglas a partir de conjuntos de datos clasificados. En este caso analizamos la familia de Algoritmos TDIDT (Top Down Induction Trees) que permite obtener árboles de decisión que particionan un grupo de datos en clases predefinidas.
Los árboles de decisión de la familia TDIDT se construyen a partir del método Hunt:



\begin{verbatim}
Se parte de un conjunto T de datos de entrenamiento. 
Dadas las clases {C1, C2,. . ., Ck}, existen tres posibilidades:
1. T contiene uno o más casos, todos pertenecientes a un única clase Cj:
   El árbol de decisión para T es una hoja identificando la clase Cj .
2. T no contiene ningún caso: El árbol de decisión es una hoja, pero la clase 
   asociada debe ser determinada por información que no pertenece a T. Por ejemplo, 
   una hoja puede escogerse de acuerdo a conocimientos de base del dominio, como ser 
   la clase mayoritaria.
3. T contiene casos pertenecientes a varias clases: Se refina T en subconjuntos
   de casos que tiendan hacia una colección de casos de una única clase. 
   Se elige una prueba basada en un único atributo, que tiene uno o más resultados, 
   mutuamente   excluyentes {O1, O2,. . ., On}. T se particiona en los subconjuntos
   T1, T2,. . ., Tn donde Ti contiene todos los casos de T que tienen el resultado
   Oi para la prueba elegida. 
   El árbol de decisión para T consiste en un nodo de decisión identificando la prueba, 
   con una rama para cada resultado posible. El mecanismo de construcción del árbol 
   se aplica recursivamente a cada subconjunto de datos de entrenamientos, para que la 
   i-ésima rama lleve al árbol de decisión construido por el subconjunto Ti de datos 
   de entrenamiento.
\end{verbatim} 
Los árboles generados a partir de ID3 y c4.5 se obtienen mediante la aplicación de este algoritmo. A medida que se avanza se obtiene una partición del conjunto de ejemplos en subconjuntos  sobre la cual es más sencillo trabajar. La partición se realiza según una prueba realizada sobre el “mejor” atributo. Para calcular cuál es el mejor atributo en cada partición, se utilizaron tanto la ganancia como la proporción de ganancia. Además, en el caso del C4.5 se podan los árboles obtenidos utilizando el método descripto para evitar el sobreajuste.
A partir de los árboles obtenidos se pueden obtener reglas que permitan una mejor interpretación del resultado obtenido y una forma más fácil de realizar la clasificación de nuevas instancias.


\section{Conceptos}
\subsection{Entropía}
La entropía determina la azarosidad o desestructuración de los datos, o dicho de otra forma, es la cantidad de información esperada al observar un evento que ocurre según una distribución de probabilidad. Es una medida de la incertidumbre dada una distribución de probabilidades. La entropía es inversamente proporcional a la probabilidad de un suceso (si un suceso es seguro, la entropía es nula).
La entropía de un subconjunto está dada por:

\[H(S) = [ - P+. log(P+) ] – [ P- . log(P-) ]\]

Donde P+ es la probabilidad de que un ejemplo tomado al azar sea positivo, P- la probabilidad de que sea negativo.

\subsection{Ganancia de información}
La ganancia de información indica la disminución en entropía al realizar una subdivisión y se calcula como:
\[Ganancia (S, atributo) = H(S) – H(S, atributo)\]
Siendo H(S) el valor de la entropía a priori y H(S,atributo) el valor de la entropía del sistema de subconjuntos generados por la partición del atributo.
Favorece a los atributos que tienen muchos valores frente a los que tienen pocos valores.
\subsection{Información de división}

Es la entropía del conjunto con respecto al conjunto.
\[L_division (atributo) = \sum [ - P+ . log (P+) ]\]
La información de división penaliza los atributos con muchos valores uniformemente distribuidos.

\subsection{Proporción de ganancia}

La proporción de ganancia se calcula de la siguiente forma:
\[Proporcion de Ganancia (atributo) = Ganancia(s, atributo) / L_Division (atributo)\]
El atributo que maximice la proporción de ganancia o la ganancia, es el atributo por el cual se dividirá el árbol, decidiendo sobre el resultado de los demás (evitando que se favorezcan atributos con muchos valores, como ocurriría si solo aplicamos como criterio la ganancia de información).
\subsection{Sobreajuste (overfitting)}

A medida que se divide un nodo creando un sub árbol, se añaden niveles a los arboles de clasificación. Se pueden agregar gran cantidad de niveles, de forma tal que sea más precisa la clasificación, pero al mismo tiempo aumenta el error por no poder generalizar al conjunto de prueba. Este efecto puede deberse a la presencia de ruido o a la utilización de un conjunto pequeño. Para solucionarlo se utiliza una poda o corte.

\subsection{Calidad de las reglas}

Para conocer la calidad de las reglas obtenidas, se tiene en cuenta tres valores importantes: el soporte, la confianza y la captura. \\
\begin{itemize}

\item \textbf{Soporte:} Es la relación que existe entre la totalidad de las observaciones que se aplica la regla y la totalidad de observaciones procesadas, expresada en porcentaje.
\item \textbf{Confianza:} Relación que existe entre la cantidad de observaciones de la clase mayoritaria afectadas por la regla y la totalidad de observaciones afectadas por la regla.  
\item \textbf{Captura:} Relación que existe entre la cantidad de observaciones de la clase mayoritaria que fueron afectadas por la regla y la cantidad total de observaciones procesadas pertenecientes a la clase mayoritaria. \end{itemize}

\section{Algoritmos}

\subsection{ID3}

EL ID3 o Induction Decision Trees es un algoritmo desarrollado por Quinlan para construir un modelo de decisión mediante aprendizaje supervisado a partir de un conjunto de ejemplos. Estos ejemplos o tuplas están  constituidos por un conjunto de atributos y un clasificador o clase. 
\subsubsection{Características generales}

\begin{itemize}
\item Los dominios de los atributos y de las clases deben ser discretos.
\item Las clases deben ser disjuntas. 
\item Las primeras versiones del ID3 generaban descripciones únicamente para dos clases, (positiva y negativa). En las versiones posteriores, se eliminó esta restricción, pero se mantuvo la restricción de clases disjuntas. 
\item Tiene una buena performance en un amplio rango de aplicaciones de diversos dominios, como el dominio médico, el artificial y el análisis de juegos de ajedrez. 
\item El nivel de precisión en la clasificación generalmente es alto. 
\end{itemize}

El algoritmo ID3 utiliza la ganancia de información, para la elección del atributo, sin embargo estos atributos no son buenos predictores de la función objetivo para nuevos ejemplos, ya que dicha ganancia introduce un sesgo que favorece a los atributos con muchos valores distintos, debido a que dividen el conjunto de ejemplos en muchos subconjuntos, lo que hace que la ganancia de información sea alta.
ID3 tiene las siguientes desventajas:
\begin{itemize}
\item No trabaja con valores continuos.
\item Aún cuando se cuente con conocimientos de  dominio o conocimientos previos, el sistema no hace uso de ellos. 
\item A veces, los árboles son demasiado frondosos, lo cual conlleva una difícil interpretación. En esos casos pueden ser transformados en reglas de decisión para hacerlos más comprensibles.
\end{itemize}


Un pseudocódigo del algoritmo es el siguiente:
\begin{verbatim}
Funcion ID3
R= conjunto de atributos no clasificados.
C= atributo clasificador.
S= conjunto de entrenamiento, 
devuelve un árbol de decisión.
Si S está vacío,
devolver un único nodo con Valor Falla;

Si todos los registros de S tienen el mismo valor para el atributo clasificador,
Devolver un único nodo con dicho valor;

Si R está vacío, entonces
devolver un único nodo con el valor más frecuente del atributo clasificador en los registros de
S [Nota: habrá errores, es decir, registros que no estarán bien clasificados en este caso];

Si R no está vacío, entonces
D <- atributo con mayor Ganancia (D, S) entre los atributos de R;
Sean {dj| j=1,2, .., m} los valores del atributo D;
Sean {Sj| j=1,2, .., m} los subconjuntos de S correspondientes a los valores de dj respectivamente;
Devolver un árbol con la raíz nombrada como D y con los arcos nombrados d1, d2, .., dm que
van respectivamente a los árboles ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm); 

\end{verbatim} 



\subsection{C4.5}

El C4.5 es una extensión del ID3, propuesto por Quinlan en 1993. C4.5 genera un árbol de decisión a partir de los datos mediante particiones realizadas recursivamente, según la estrategia de profundidad-primero (depth-first). 
El algoritmo C4.5 utiliza como heurística para elegir el mejor atributo al realizar la partición la proporción de ganancia (gainratio). El algoritmo considera todas las pruebas posibles que pueden dividir el conjunto de datos y selecciona la prueba que le haya generado la mayor ganancia de información.
Para cada atributo discreto, se considera una prueba con n resultados, siendo n el número de valores posibles quepuede tomar el atributo. 
Para cada atributo continuo, se realiza una prueba binaria (1,0) sobrecada uno de los valores que toma el atributo en los datos. En cada nodo, el sistema debe decidircual prueba escoge para dividir los datos.
\subsubsection{Características generales}

\begin{itemize}
\item Permite trabajar con valores continuos para los atributos, separando los posibles resultados en dos ramas: una para aquellos Ai<=N y  otra para Ai>N.
\item Los árboles son menos frondosos que los obtenidos con ID3 porque cada hoja no cubre una clase en particular sino una distribución de clases, lo cual los hace menos profundos y menos frondosos. 
\item Realiza una post poda. La post poda se realiza luego de haber sido generado el árbol de clasificación, podando las ramas necesarias para mejorar el rendimiento y a su vez obtener un árbol más sencillo y cómodo de estudiar.
\item Se basan en la utilización del criterio de proporción de ganancia (gain ratio). De esta manera se consigue evitar que las variables con mayor número de categorías salgan beneficiadas en la selección.
\end{itemize}


El algoritmo fue implentado en numerosos lenguajes, uno de los más conocidos es el J48 desarrollado en JAVA incluido en WEKA.
Un pseudocódigo del algoritmo es el siguiente:

\begin{verbatim}
Funcion ID3
R= conjunto de atributos no clasificados.
C= atributo clasificador.
S= conjunto de entrenamiento, 
devuelve un árbol de decisión.
Si S está vacío,
devolver un único nodo con Valor Falla;

Si todos los registros de S tienen el mismo valor para el atributo clasificador,
Devolver un único nodo con dicho valor;

Si R está vacío, entonces
devolver un único nodo con el valor más frecuente del atributo clasificador en los registros de
S [Nota: habrá errores, es decir, registros que no estarán bien clasificados en este caso];

Si R no está vacío, entonces
D <- atributo con mayor Ganancia (D, S) entre los atributos de R;
Sean {dj| j=1,2, .., m} los valores del atributo D;
Sean {Sj| j=1,2, .., m} los subconjuntos de S correspondientes a los valores de dj respectivamente;
Devolver un árbol con la raíz nombrada como D y con los arcos nombrados d1, d2, .., dm que
van respectivamente a los árboles ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm); \end{verbatim} 


\section{Experiencia}

\subsection{Objetivo}

Se utilizará WEKA y RapidMiner para probar los algoritmos ID3 y C4.5. A partir del análisis de los resultados, será posible obtener conclusiones sobre los algoritmos. Para obtener los resultados sobre los cuales desarrollar el análisis se usará una base de datos que indica posibles posiciones de un tablero del juego “tic tac toe”. A partir del mismo, se obtendrán reglas y se realizarán evaluaciones del modelo para cada algoritmo de árbol de decisión.
\subsection{Descripción de la base de datos}

\begin{itemize}
\item \textbf{Fuente: }Repositorio UCI\footnote{ http://archive.ics.uci.edu/ml/datasets/Tic-Tac-Toe+Endgame}
\item \textbf{Título:} Tic-Tac-Toe Endgame database
 \item \textbf{Descripción:} codifica el set de configuraciones posibles al finalizar el juego “tic-tac-toe”. Se asume que “x” juega primero. Indica si gana “x” acuerdo a la formas posibles de obtener 3 símbolos x iguales “en línea”.
\item \textbf{Formato:} C4.5
\item \textbf{Cantidad de instancias:} 958 (posiciones posibles al final del juego)
\item \textbf{Cantidad de atributos:} 9, uno correspondiente a cada cuadrado del tablero.
\end{itemize}


\subsubsection{Rango de valores}

Todos los valores son discretos.

\begin{itemize}
\item Un valor “x” en cualquiera de los atributos significa que el cuadrado fue ocupado por x.
\item Un valor “o” en cualquiera de los atributos significa que el cuadrado fue ocupado por o.
\item Un valor “b” en cualquiera de los atributos significa que el cuadrado se encuentra libre.\end{itemize}


\subsubsection{Atributos}

Existe un atributo para cada cuadrado del tablero y se nombran de la siguiente forma:

\begin{itemize}
\item top-left-square {x,o,b}: cuadrado izquierdo superior.
\item top-middle-square {x,o,b} : cuadrado medio superior
\item top-right-square {x,o,b} : cuadrado derecho superior.
\item middle-left-square {x,o,b} : cuadrado izquierdo del centro.
\item middle-middle-square {x,o,b} : cuadrado medio del centro.
\item middle-right-square {x,o,b} : cuadrado derecho del centro.
\item bottom-left-square {x,o,b} : cuadrado izquierdo inferior.
\item bottom-middle-square {x,o,b} : cuadrado medio inferior.
\item bottom-right-square {x,o,b} : cuadrado derecho inferior.                                                        \end{itemize}


Clase: {positive,negative} : indica si gana “x” o no.

\subsubsection{Otras características}
  
\begin{itemize}
\item Distribución de la clase: 65.3 \% son “positive”, 34,7\% “negative”. 
 \item No hay atributos con valores desconocidos. \end{itemize}


\subsection{Preparación de datos}

\subsubsection{Selección de datos}

Se decidió hacer uso de todos los registros disponibles, dado que consideramos que todos representan casos dados. Asimismo, no se omitió ningún campo dado que todos se consideraron relevantes para el análisis.
\subsubsection{Limpieza de datos}

No fue necesario aplicar ninguna técnica de limpieza de datos, dado que todos los registros están completos y trabajamos bajo la hipótesis de que los mismos son correctos.
\subsubsection{Construcción de datos}

Consideramos que no es necesaria la creación de nuevos registros ya que asumimos que la base de datos con la que se trabaja contiene ejemplos de todos los casos que se desean tener en cuenta para el análisis. Los atributos ya se encuentran categorizados. Tampoco fue necesario hacer derivación de atributos.
\subsubsection{Integración de datos}

No es posible aplicar esta técnica dado que existe una única tabla que contiene todos los registros y atributos que deberán considerarse.
Formación de datos
No fue necesario realizar ningún tipo de transformación de datos dado que el formato que presentan cumple con las condiciones establecidas para el uso de las herramientas a utilizar: RapidMiner y Weka. Asimismo, los valores de los atributos a utilizar son todos discretos, por lo cual no fue necesario realizar ninguna modificación para el uso del algoritmo ID3 ni C4.5.


\subsection{Análisis de los datos}


Se utilizó la herramienta WEKA para obtener valores de los atributos de acuerdo a los  criterios proporción de ganancia y ganancia de información. Este estudio se realizó con el objetivo de entender qué atributos se utilizarán posteriormente para dividir el árbol y determinar el orden en que se utilizarán los atributos.
\begin{verbatim}
Ganancia de información
 0.08719   5 middle-middle-square
 0.01356   3 top-right-square
 0.01356   9 bottom-right-square
 0.01356   1 top-left-square
 0.01356   7 bottom-left-square
 0.00701   2 top-middle-square
 0.00701   8 bottom-middle-square
 0.00701   4 middle-left-square
 0.00701   6 middle-right-square


Selected attributes: 5,3,9,1,7,2,8,4,6 : 9
\end{verbatim} 
El último renglón determina el órden de los atributos que se utilizará en ID3. Puede haber otras combinaciones debido a que la ganancia de información es la misma para distintos atributos.
\begin{verbatim}
Proporción de ganancia
 0.05929   5 middle-middle-square
 0.00887   3 top-right-square
 0.00887   9 bottom-right-square
 0.00887   1 top-left-square
 0.00887   7 bottom-left-square
 0.00448   2 top-middle-square
 0.00448   8 bottom-middle-square
 0.00448   4 middle-left-square
 0.00448   6 middle-right-square

Selected attributes: 5,3,9,1,7,2,8,4,6 : 9\end{verbatim}


El último renglón determina el órden de los atributos que se utilizará en C4.5. Puede haber otras combinaciones debido a que la proporción de ganancia es la misma para distintos atributos.

\subsection{Aplicación de ID3}

\subsubsection{Configuración de la Herramienta}

Para la aplicación del algoritmo ID3 se decidió utilizar RapidMiner, un entorno para data mining open source. La elección se debe a que, en particular para este algoritmo y a diferencia de WEKA, es posible obtener información más precisa sobre las reglas utilizadas y sobre la eficiencia lograda.
Se configuró la herramienta mediante 4 componentes:
\begin{itemize}
\item \textbf{Read C4.5} para leer el archivo con el set de datos.
\item  \textbf{ID3:} para generar el árbol de decisión.
\begin{itemize}
\item  Criterion: information gain
\item Minimal size for Split: 1
\item Minimal leaf size: 1
\item Minimal gain: 0\end{itemize}

\item \textbf{Tree to Rule:} para obtener las reglas.
\item \textbf{Performance (classification):} para evaluar el modelo obtenido.
\item Se usó la técnica de CrossValidation, 10 folds.
\end{itemize}

\subsubsection{Resultados}

\paragraph{Árbol de decisión}

\begin{verbatim}
middle-middle-square = b
|   top-left-square = b
|   |   bottom-right-square = o: negative {positive=0, negative=8}
|   |   bottom-right-square = x: positive {positive=20, negative=0}
|   top-left-square = o
|   |   bottom-right-square = b: negative {positive=0, negative=8}
|   |   bottom-right-square = o: negative {positive=0, negative=4}
|   |   bottom-right-square = x
|   |   |   top-right-square = b
|   |   |   |   bottom-left-square = o: negative {positive=0, negative=3}
|   |   |   |   bottom-left-square = x: positive {positive=6, negative=0}
|   |   |   top-right-square = o
|   |   |   |   top-middle-square = b: positive {positive=3, negative=0}
|   |   |   |   top-middle-square = o: negative {positive=0, negative=7}
|   |   |   |   top-middle-square = x
|   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   top-right-square = x
|   |   |   |   middle-right-square = b
|   |   |   |   |   top-middle-square = b: negative {positive=0, negative=1}
|   |   |   |   |   top-middle-square = o: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = x: negative {positive=0, negative=1}
|   |   |   |   middle-right-square = o
|   |   |   |   |   top-middle-square = b: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = o: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = x: negative {positive=0, negative=1}
|   |   |   |   middle-right-square = x: positive {positive=14, negative=0}
|   top-left-square = x
|   |   bottom-right-square = b: positive {positive=20, negative=0}
|   |   bottom-right-square = o
|   |   |   top-right-square = b
|   |   |   |   bottom-left-square = o: negative {positive=0, negative=3}
|   |   |   |   bottom-left-square = x: positive {positive=6, negative=0}
|   |   |   top-right-square = o
|   |   |   |   middle-right-square = b: positive {positive=3, negative=0}
|   |   |   |   middle-right-square = o: negative {positive=0, negative=7}
|   |   |   |   middle-right-square = x
|   |   |   |   |   top-middle-square = b: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = o: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = x: negative {positive=0, negative=1}
|   |   |   top-right-square = x
|   |   |   |   top-middle-square = b
|   |   |   |   |   middle-right-square = b: negative {positive=0, negative=1}
|   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   top-middle-square = o
|   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   top-middle-square = x: positive {positive=14, negative=0}
|   |   bottom-right-square = x: positive {positive=16, negative=0}
middle-middle-square = o
|   top-left-square = b
|   |   bottom-right-square = b: negative {positive=0, negative=12}
|   |   bottom-right-square = o: negative {positive=0, negative=5}
|   |   bottom-right-square = x
|   |   |   top-middle-square = b
|   |   |   |   bottom-middle-square = b
|   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = o
|   |   |   |   |   |   middle-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-right-square = x: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = x: negative {positive=0, negative=1}
|   |   |   |   bottom-middle-square = o: positive {positive=3, negative=0}
|   |   |   |   bottom-middle-square = x
|   |   |   |   |   bottom-left-square = b: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   top-right-square = o: negative {positive=0, negative=2}
|   |   |   |   |   |   top-right-square = x: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = x: positive {positive=5, negative=0}
|   |   |   top-middle-square = o
|   |   |   |   bottom-middle-square = b: positive {positive=3, negative=0}
|   |   |   |   bottom-middle-square = o: negative {positive=0, negative=7}
|   |   |   |   bottom-middle-square = x
|   |   |   |   |   bottom-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   top-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   top-right-square = x: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = x: positive {positive=7, negative=0}
|   |   |   top-middle-square = x
|   |   |   |   middle-left-square = b
|   |   |   |   |   middle-right-square = b: negative {positive=0, negative=1}
|   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = x
|   |   |   |   |   |   top-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   top-right-square = x: positive {positive=1, negative=0}
|   |   |   |   middle-left-square = o
|   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-right-square = o: negative {positive=0, negative=5}
|   |   |   |   |   middle-right-square = x
|   |   |   |   |   |   top-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   top-right-square = x: positive {positive=2, negative=0}
|   |   |   |   middle-left-square = x: negative {positive=0, negative=3}
|   top-left-square = o
|   |   bottom-right-square = b: negative {positive=0, negative=5}
|   |   bottom-right-square = o: negative {positive=0, negative=50}
|   |   bottom-right-square = x
|   |   |   top-middle-square = b
|   |   |   |   top-right-square = b: positive {positive=3, negative=0}
|   |   |   |   top-right-square = o
|   |   |   |   |   bottom-left-square = o: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = x: positive {positive=2, negative=0}
|   |   |   |   top-right-square = x: positive {positive=9, negative=0}
|   |   |   top-middle-square = o
|   |   |   |   top-right-square = b
|   |   |   |   |   bottom-middle-square = o: negative {positive=0, negative=1}
|   |   |   |   |   bottom-middle-square = x: positive {positive=2, negative=0}
|   |   |   |   top-right-square = o: negative {positive=0, negative=2}
|   |   |   |   top-right-square = x
|   |   |   |   |   bottom-middle-square = b: positive {positive=2, negative=0}
|   |   |   |   |   bottom-middle-square = o: negative {positive=0, negative=1}
|   |   |   |   |   bottom-middle-square = x: positive {positive=5, negative=0}
|   |   |   top-middle-square = x
|   |   |   |   bottom-left-square = b
|   |   |   |   |   middle-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   middle-right-square = x: positive {positive=2, negative=0}
|   |   |   |   bottom-left-square = o
|   |   |   |   |   bottom-middle-square = b
|   |   |   |   |   |   top-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   top-right-square = x: positive {positive=1, negative=0}
|   |   |   |   |   bottom-middle-square = o: positive {positive=1, negative=0}
|   |   |   |   |   bottom-middle-square = x: negative {positive=0, negative=5}
|   |   |   |   bottom-left-square = x
|   |   |   |   |   bottom-middle-square = b: negative {positive=0, negative=1}
|   |   |   |   |   bottom-middle-square = o
|   |   |   |   |   |   middle-left-square = o: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-left-square = x: negative {positive=0, negative=2}
|   |   |   |   |   bottom-middle-square = x: positive {positive=5, negative=0}
|   top-left-square = x
|   |   top-right-square = b
|   |   |   middle-left-square = b
|   |   |   |   middle-right-square = b: negative {positive=0, negative=1}
|   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   middle-right-square = x: negative {positive=0, negative=2}
|   |   |   middle-left-square = o
|   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   middle-right-square = o: negative {positive=0, negative=9}
|   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   middle-left-square = x
|   |   |   |   bottom-left-square = b: negative {positive=0, negative=2}
|   |   |   |   bottom-left-square = o: negative {positive=0, negative=2}
|   |   |   |   bottom-left-square = x: positive {positive=14, negative=0}
|   |   top-right-square = o
|   |   |   bottom-left-square = b: negative {positive=0, negative=3}
|   |   |   bottom-left-square = o: negative {positive=0, negative=30}
|   |   |   bottom-left-square = x
|   |   |   |   middle-left-square = b
|   |   |   |   |   top-middle-square = b: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = o
|   |   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   |   top-middle-square = x: negative {positive=0, negative=1}
|   |   |   |   middle-left-square = o
|   |   |   |   |   top-middle-square = b: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = o: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = x: negative {positive=0, negative=4}
|   |   |   |   middle-left-square = x: positive {positive=17, negative=0}
|   |   top-right-square = x
|   |   |   top-middle-square = b
|   |   |   |   bottom-middle-square = b
|   |   |   |   |   bottom-left-square = b: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = o: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = x
|   |   |   |   |   |   middle-left-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-left-square = x: positive {positive=1, negative=0}
|   |   |   |   bottom-middle-square = o
|   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = o
|   |   |   |   |   |   middle-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-right-square = x: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = x
|   |   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   bottom-middle-square = x: negative {positive=0, negative=3}
|   |   |   top-middle-square = o
|   |   |   |   bottom-middle-square = b
|   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = o
|   |   |   |   |   |   middle-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-right-square = x: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = x: positive {positive=2, negative=0}
|   |   |   |   bottom-middle-square = o: negative {positive=0, negative=12}
|   |   |   |   bottom-middle-square = x
|   |   |   |   |   bottom-left-square = b: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   middle-left-square = o: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-left-square = x: negative {positive=0, negative=2}
|   |   |   |   |   bottom-left-square = x
|   |   |   |   |   |   middle-left-square = o: negative {positive=0, negative=2}
|   |   |   |   |   |   middle-left-square = x: positive {positive=1, negative=0}
|   |   |   top-middle-square = x: positive {positive=38, negative=0}
middle-middle-square = x
|   top-left-square = b
|   |   bottom-right-square = b: positive {positive=30, negative=0}
|   |   bottom-right-square = o
|   |   |   middle-right-square = b
|   |   |   |   bottom-left-square = b: positive {positive=2, negative=0}
|   |   |   |   bottom-left-square = o
|   |   |   |   |   bottom-middle-square = o: negative {positive=0, negative=3}
|   |   |   |   |   bottom-middle-square = x: positive {positive=3, negative=0}
|   |   |   |   bottom-left-square = x: positive {positive=7, negative=0}
|   |   |   middle-right-square = o
|   |   |   |   top-right-square = b: positive {positive=3, negative=0}
|   |   |   |   top-right-square = o: negative {positive=0, negative=7}
|   |   |   |   top-right-square = x
|   |   |   |   |   bottom-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-left-square = x: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = x: positive {positive=7, negative=0}
|   |   |   middle-right-square = x
|   |   |   |   middle-left-square = b
|   |   |   |   |   top-middle-square = b: negative {positive=0, negative=1}
|   |   |   |   |   top-middle-square = o: positive {positive=1, negative=0}
|   |   |   |   |   top-middle-square = x
|   |   |   |   |   |   top-right-square = b: negative {positive=0, negative=1}
|   |   |   |   |   |   top-right-square = o: positive {positive=1, negative=0}
|   |   |   |   middle-left-square = o
|   |   |   |   |   bottom-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   top-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   top-right-square = x: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = x: positive {positive=2, negative=0}
|   |   |   |   middle-left-square = x: positive {positive=14, negative=0}
|   |   bottom-right-square = x: positive {positive=20, negative=0}
|   top-left-square = o
|   |   bottom-right-square = b
|   |   |   top-middle-square = b
|   |   |   |   middle-left-square = b: positive {positive=2, negative=0}
|   |   |   |   middle-left-square = o
|   |   |   |   |   bottom-left-square = o: negative {positive=0, negative=3}
|   |   |   |   |   bottom-left-square = x: positive {positive=3, negative=0}
|   |   |   |   middle-left-square = x: positive {positive=7, negative=0}
|   |   |   top-middle-square = o
|   |   |   |   top-right-square = b: positive {positive=3, negative=0}
|   |   |   |   top-right-square = o: negative {positive=0, negative=7}
|   |   |   |   top-right-square = x
|   |   |   |   |   bottom-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   middle-left-square = o: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-left-square = x: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = x: positive {positive=7, negative=0}
|   |   |   top-middle-square = x
|   |   |   |   bottom-middle-square = b
|   |   |   |   |   top-right-square = b: negative {positive=0, negative=1}
|   |   |   |   |   top-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   top-right-square = x
|   |   |   |   |   |   middle-right-square = b: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   bottom-middle-square = o
|   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = o
|   |   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   |   middle-left-square = x: positive {positive=2, negative=0}
|   |   |   |   bottom-middle-square = x: positive {positive=14, negative=0}
|   |   bottom-right-square = o
|   |   |   top-right-square = b: positive {positive=14, negative=0}
|   |   |   top-right-square = o
|   |   |   |   top-middle-square = b
|   |   |   |   |   middle-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   middle-right-square = x: positive {positive=2, negative=0}
|   |   |   |   top-middle-square = o: negative {positive=0, negative=2}
|   |   |   |   top-middle-square = x
|   |   |   |   |   middle-right-square = b: positive {positive=2, negative=0}
|   |   |   |   |   middle-right-square = o: negative {positive=0, negative=1}
|   |   |   |   |   middle-right-square = x: positive {positive=5, negative=0}
|   |   |   top-right-square = x
|   |   |   |   bottom-left-square = b: positive {positive=4, negative=0}
|   |   |   |   bottom-left-square = o
|   |   |   |   |   middle-left-square = b
|   |   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   |   middle-left-square = o: negative {positive=0, negative=2}
|   |   |   |   |   middle-left-square = x
|   |   |   |   |   |   middle-right-square = b: negative {positive=0, negative=1}
|   |   |   |   |   |   middle-right-square = o: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = x: positive {positive=2, negative=0}
|   |   |   |   bottom-left-square = x: positive {positive=19, negative=0}
|   |   bottom-right-square = x
|   |   |   top-right-square = b
|   |   |   |   middle-left-square = b: positive {positive=2, negative=0}
|   |   |   |   middle-left-square = o
|   |   |   |   |   bottom-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = o: negative {positive=0, negative=5}
|   |   |   |   |   bottom-left-square = x: positive {positive=2, negative=0}
|   |   |   |   middle-left-square = x: positive {positive=3, negative=0}
|   |   |   top-right-square = o
|   |   |   |   top-middle-square = b
|   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   middle-left-square = o
|   |   |   |   |   |   middle-right-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-right-square = x: negative {positive=0, negative=1}
|   |   |   |   |   middle-left-square = x: positive {positive=2, negative=0}
|   |   |   |   top-middle-square = o: negative {positive=0, negative=12}
|   |   |   |   top-middle-square = x
|   |   |   |   |   bottom-middle-square = b: negative {positive=0, negative=1}
|   |   |   |   |   bottom-middle-square = o
|   |   |   |   |   |   bottom-left-square = o: positive {positive=1, negative=0}
|   |   |   |   |   |   bottom-left-square = x: negative {positive=0, negative=2}
|   |   |   |   |   bottom-middle-square = x: positive {positive=5, negative=0}
|   |   |   top-right-square = x
|   |   |   |   bottom-left-square = b: positive {positive=3, negative=0}
|   |   |   |   bottom-left-square = o
|   |   |   |   |   middle-right-square = b: negative {positive=0, negative=3}
|   |   |   |   |   middle-right-square = o: negative {positive=0, negative=4}
|   |   |   |   |   middle-right-square = x: positive {positive=3, negative=0}
|   |   |   |   bottom-left-square = x: positive {positive=10, negative=0}
|   top-left-square = x
|   |   bottom-right-square = b: positive {positive=20, negative=0}
|   |   bottom-right-square = o
|   |   |   top-right-square = b
|   |   |   |   bottom-left-square = b: positive {positive=2, negative=0}
|   |   |   |   bottom-left-square = o
|   |   |   |   |   bottom-middle-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-middle-square = o: negative {positive=0, negative=5}
|   |   |   |   |   bottom-middle-square = x: positive {positive=2, negative=0}
|   |   |   |   bottom-left-square = x: positive {positive=3, negative=0}
|   |   |   top-right-square = o
|   |   |   |   middle-right-square = b
|   |   |   |   |   bottom-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   bottom-left-square = o
|   |   |   |   |   |   middle-left-square = b: positive {positive=1, negative=0}
|   |   |   |   |   |   middle-left-square = x: negative {positive=0, negative=1}
|   |   |   |   |   bottom-left-square = x: positive {positive=2, negative=0}
|   |   |   |   middle-right-square = o: negative {positive=0, negative=12}
|   |   |   |   middle-right-square = x
|   |   |   |   |   middle-left-square = b: negative {positive=0, negative=1}
|   |   |   |   |   middle-left-square = o
|   |   |   |   |   |   bottom-left-square = o: positive {positive=1, negative=0}
|   |   |   |   |   |   bottom-left-square = x: negative {positive=0, negative=2}
|   |   |   |   |   middle-left-square = x: positive {positive=5, negative=0}
|   |   |   top-right-square = x
|   |   |   |   bottom-left-square = b: positive {positive=3, negative=0}
|   |   |   |   bottom-left-square = o
|   |   |   |   |   top-middle-square = b: negative {positive=0, negative=3}
|   |   |   |   |   top-middle-square = o: negative {positive=0, negative=4}
|   |   |   |   |   top-middle-square = x: positive {positive=3, negative=0}
|   |   |   |   bottom-left-square = x: positive {positive=10, negative=0}
|   |   bottom-right-square = x: positive {positive=90, negative=0}     

                                                              \end{verbatim} 

\paragraph{Reglas}

Se obtuvieron un 218 reglas, de acuerdo al árbol expuesto en la sección anterior. No se transcriben todas las reglas, por cuestiones de espacio. Se mencionan algunas de las reglas más relevantes obtenidas.


\begin{longtable}{|>{\small}p{3cm}|l|l|l|l|l|}
\hline
\multicolumn{1}{|c|}{\textbf{Regla}} & \textbf{positive} & \textbf{negative} & \textbf{Soporte} & \textbf{Confianza} & \textbf{Captura} \\ \hline
IF middle-middle-square = b AND
top-left-square = b AND
bottom-right-square = x: positive \{positive=20, negative=0\} & 20 & 0 & 2,09\% & 100,00\% & 3,19\% \\ \hline
IF middle-middle-square = b AND
top-left-square = x AND
bottom-right-square = b: positive \{positive=20, negative=0\} & 20 & 0 & 2,09\% & 100,00\% & 3,19\% \\ \hline
IF middle-middle-square = o AND
top-left-square = o AND
  bottom-right-square = o: negative \{positive=0, negative=50\} & 0 & 50 & 5,22\% & 100,00\% & 7,99\% \\ \hline
IF middle-middle-square = o AND
top-left-square = x AND
top-right-square = o AND
bottom-left-square = o: negative \{positive=0, negative=30\} & 0 & 50 & 5,22\% & 100,00\% & 7,99\% \\ \hline
IF middle-middle-square = x AND
top-left-square = x AND
bottom-right-square = x: positive \{positive=90, negative=0\} & 90 & 0 & 9,39\% & 100,00\% & 14,38\% \\ \hline
IF middle-middle-square = x AND
top-left-square = b AND
bottom-right-square = o AND
middle-right-square = x AND
bottom-right-square = x: positive \{positive=20, negative=0\} & 20 & 0 & 2,09\% & 100,00\% & 3,19\% \\ \hline
\end{longtable}




\paragraph{Evaluación del modelo}

\begin{itemize}
\item Tiempo de ejecución: 2 segundos.
\item Accuracy : 798(83.2985 %)
\item Kappa statistic: 0.689.
\item Mean absolute error: 0.1429.
\item Root mean squared error: 0.378.
\item Relative absolute error: 32.3932 %.
\item Root relative squared error: 80.4304 %.
\item UnClassified Instances : 27 (2.8184 %)
\end{itemize}


\subsection{Aplicación de C4.5}

\subsubsection{Configuración de la herramienta}

Para la aplicación del algoritmo C4.5 se utilizó el entorno para minería de datos WEKA, desarrollado por la Universidad de Waikato. Se descartó RapidMiner, debido a que la implementación que ofrece este último no es tan fiel al algoritmo presentado por Quinlan.
En la pestaña “Classify”:
\begin{itemize}
\item Nuevamente se utilizó la técnica CrossValidation, 10 folds.
\item Choose: PART. Este es un algoritmo que construye un árbol de decisión usando C4.5 y luego extrae las reglas a partir del mismo. Se usaron las opciones por defecto.
\item Binay splits: false. 
\item Confidence factor: 0.25
\item Debug: false
\item Min num obj: 2
\item Num folds: 3
\item Reduced Error pruned: false
\item Seed: 1
\item Unpruned: false
\end{itemize}

\subsubsection{Resultados}

\paragraph{Arbol de decisión}

\begin{verbatim}

middle-middle-square = x
|   top-left-square = x
|   |   bottom-right-square = x: positive (90.0)
|   |   bottom-right-square = o
|   |   |   top-right-square = x
|   |   |   |   bottom-left-square = x: positive (10.0)
|   |   |   |   bottom-left-square = o
|   |   |   |   |   top-middle-square = x: positive (3.0)
|   |   |   |   |   top-middle-square = o: negative (4.0)
|   |   |   |   |   top-middle-square = b: negative (3.0)
|   |   |   |   bottom-left-square = b: positive (3.0)
|   |   |   top-right-square = o
|   |   |   |   middle-right-square = x
|   |   |   |   |   middle-left-square = x: positive (5.0)
|   |   |   |   |   middle-left-square = o: negative (3.0/1.0)
|   |   |   |   |   middle-left-square = b: negative (1.0)
|   |   |   |   middle-right-square = o: negative (12.0)
|   |   |   |   middle-right-square = b: positive (5.0/1.0)
|   |   |   top-right-square = b
|   |   |   |   bottom-left-square = x: positive (3.0)
|   |   |   |   bottom-left-square = o
|   |   |   |   |   bottom-middle-square = x: positive (2.0)
|   |   |   |   |   bottom-middle-square = o: negative (5.0)
|   |   |   |   |   bottom-middle-square = b: positive (1.0)
|   |   |   |   bottom-left-square = b: positive (2.0)
|   |   bottom-right-square = b: positive (20.0)
|   top-left-square = o
|   |   top-right-square = x
|   |   |   bottom-left-square = x: positive (45.0)
|   |   |   bottom-left-square = o: negative (26.0/10.0)
|   |   |   bottom-left-square = b: positive (9.0)
|   |   top-right-square = o
|   |   |   top-middle-square = x: positive (26.0/4.0)
|   |   |   top-middle-square = o: negative (21.0)
|   |   |   top-middle-square = b: positive (11.0/2.0)
|   |   top-right-square = b
|   |   |   middle-left-square = x: positive (19.0)
|   |   |   middle-left-square = o
|   |   |   |   bottom-left-square = x: positive (4.0)
|   |   |   |   bottom-left-square = o: negative (7.0)
|   |   |   |   bottom-left-square = b: positive (3.0)
|   |   |   middle-left-square = b: positive (7.0)
|   top-left-square = b
|   |   bottom-right-square = x: positive (20.0)
|   |   bottom-right-square = o
|   |   |   middle-right-square = x: positive (23.0/3.0)
|   |   |   middle-right-square = o
|   |   |   |   top-right-square = x: positive (10.0/1.0)
|   |   |   |   top-right-square = o: negative (7.0)
|   |   |   |   top-right-square = b: positive (3.0)
|   |   |   middle-right-square = b
|   |   |   |   bottom-left-square = x: positive (7.0)
|   |   |   |   bottom-left-square = o
|   |   |   |   |   bottom-middle-square = x: positive (3.0)
|   |   |   |   |   bottom-middle-square = o: negative (3.0)
|   |   |   |   |   bottom-middle-square = b: positive (0.0)
|   |   |   |   bottom-left-square = b: positive (2.0)
|   |   bottom-right-square = b: positive (30.0)
middle-middle-square = o
|   top-left-square = x
|   |   top-right-square = x
|   |   |   top-middle-square = x: positive (38.0)
|   |   |   top-middle-square = o
|   |   |   |   bottom-middle-square = x: negative (7.0/2.0)
|   |   |   |   bottom-middle-square = o: negative (12.0)
|   |   |   |   bottom-middle-square = b: positive (5.0/1.0)
|   |   |   top-middle-square = b
|   |   |   |   middle-left-square = x: positive (4.0/1.0)
|   |   |   |   middle-left-square = o
|   |   |   |   |   middle-right-square = x: positive (2.0)
|   |   |   |   |   middle-right-square = o: negative (6.0)
|   |   |   |   |   middle-right-square = b: negative (0.0)
|   |   |   |   middle-left-square = b: positive (1.0)
|   |   top-right-square = o
|   |   |   bottom-left-square = x
|   |   |   |   middle-left-square = x: positive (17.0)
|   |   |   |   middle-left-square = o: negative (6.0/2.0)
|   |   |   |   middle-left-square = b: positive (4.0/2.0)
|   |   |   bottom-left-square = o: negative (30.0)
|   |   |   bottom-left-square = b: negative (3.0)
|   |   top-right-square = b
|   |   |   bottom-left-square = x
|   |   |   |   middle-left-square = x: positive (14.0)
|   |   |   |   middle-left-square = o: negative (7.0/1.0)
|   |   |   |   middle-left-square = b: negative (3.0/1.0)
|   |   |   bottom-left-square = o: negative (3.0)
|   |   |   bottom-left-square = b: negative (6.0)
|   top-left-square = o
|   |   bottom-right-square = x
|   |   |   top-middle-square = x
|   |   |   |   bottom-left-square = x
|   |   |   |   |   bottom-middle-square = x: positive (5.0)
|   |   |   |   |   bottom-middle-square = o: negative (3.0/1.0)
|   |   |   |   |   bottom-middle-square = b: negative (1.0)
|   |   |   |   bottom-left-square = o: negative (8.0/2.0)
|   |   |   |   bottom-left-square = b: positive (3.0/1.0)
|   |   |   top-middle-square = o
|   |   |   |   top-right-square = x: positive (8.0/1.0)
|   |   |   |   top-right-square = o: negative (2.0)
|   |   |   |   top-right-square = b: positive (3.0/1.0)
|   |   |   top-middle-square = b: positive (15.0/1.0)
|   |   bottom-right-square = o: negative (50.0)
|   |   bottom-right-square = b: negative (5.0)
|   top-left-square = b
|   |   top-middle-square = x: negative (26.0/5.0)
|   |   top-middle-square = o
|   |   |   bottom-middle-square = x: positive (10.0/1.0)
|   |   |   bottom-middle-square = o: negative (12.0)
|   |   |   bottom-middle-square = b: positive (3.0)
|   |   top-middle-square = b: positive (18.0/7.0)
middle-middle-square = b
|   top-left-square = x
|   |   bottom-right-square = x: positive (16.0)
|   |   bottom-right-square = o
|   |   |   top-right-square = x: positive (20.0/3.0)
|   |   |   top-right-square = o
|   |   |   |   middle-right-square = x: positive (3.0/1.0)
|   |   |   |   middle-right-square = o: negative (7.0)
|   |   |   |   middle-right-square = b: positive (3.0)
|   |   |   top-right-square = b
|   |   |   |   bottom-left-square = x: positive (6.0)
|   |   |   |   bottom-left-square = o: negative (3.0)
|   |   |   |   bottom-left-square = b: positive (0.0)
|   |   bottom-right-square = b: positive (20.0)
|   top-left-square = o
|   |   bottom-right-square = x
|   |   |   top-right-square = x: positive (20.0/3.0)
|   |   |   top-right-square = o
|   |   |   |   top-middle-square = x: positive (3.0/1.0)
|   |   |   |   top-middle-square = o: negative (7.0)
|   |   |   |   top-middle-square = b: positive (3.0)
|   |   |   top-right-square = b
|   |   |   |   bottom-left-square = x: positive (6.0)
|   |   |   |   bottom-left-square = o: negative (3.0)
|   |   |   |   bottom-left-square = b: positive (0.0)
|   |   bottom-right-square = o: negative (4.0)
|   |   bottom-right-square = b: negative (8.0)
|   top-left-square = b
|   |   bottom-right-square = x: positive (20.0)
|   |   bottom-right-square = o: negative (8.0)
|   |   bottom-right-square = b: positive (0.0)                                               \end{verbatim} 

\paragraph{Reglas}

Se obtuvieron 50 reglas.

\begin{longtable}{|p{3cm}|l|l|l|l|l|l|l|l|l|}
\hline
\multicolumn{1}{|c|}{\textbf{Regla}} & \multicolumn{ 5}{c|}{\textbf{positive}} & \textbf{negative} & \textbf{Soporte} & \textbf{Confianza} & \textbf{Captura} \\ \hline
middle-middle-square = x AND
top-left-square = b AND
bottom-right-square = b: positive (30.0) & \multicolumn{ 5}{c|}{30} & 0 & 3,13\% & 100,00\% & 4,79\% \\ \hline
middle-middle-square = x AND
top-right-square = b AND
bottom-left-square = b: positive (28.0) & \multicolumn{ 5}{c|}{28} & 0 & 2,92\% & 100,00\% & 4,47\% \\ \hline
top-left-square = o AND
bottom-right-square = b AND
middle-left-square = o: negative (11.0) & \multicolumn{ 5}{c|}{0} & 11 & 1,15\% & 100,00\% & 1,76\% \\ \hline
top-right-square = o AND
bottom-left-square = o AND
middle-middle-square = o: negative (50.0) & \multicolumn{ 5}{c|}{0} & 50 & 5,22\% & 100,00\% & 7,99\% \\ \hline
middle-middle-square = x AND
top-left-square = x AND
bottom-right-square = x: positive (80.0) & \multicolumn{ 5}{c|}{80} & 0 & 8,35\% & 100,00\% & 12,78\% \\ \hline
middle-middle-square = x AND
top-right-square = x AND
bottom-left-square = x: positive (79.0) & \multicolumn{ 5}{c|}{79} & 0 & 8,25\% & 100,00\% & 12,62\% \\ \hline
middle-middle-square = b AND
top-left-square = x AND
bottom-right-square = o AND
top-right-square = x: positive (20.0/3.0) & \multicolumn{ 5}{c|}{20} & 3 & 2,40\% & 86,96\% & 3,19\% \\ \hline
middle-middle-square = b AND
bottom-right-square = x AND
top-left-square = o AND
top-right-square = x: positive (20.0/3.0) & \multicolumn{ 5}{c|}{20} & 3 & 2,40\% & 86,96\% & 3,19\% \\ \hline
middle-middle-square = b AND
top-left-square = x AND
bottom-right-square = b: positive (20.0) & \multicolumn{ 5}{c|}{20} & 0 & 2,09\% & 100,00\% & 3,19\% \\ \hline
middle-middle-square = x AND
top-left-square = b AND
bottom-right-square = o AND
middle-right-square = x: positive (18.0/3.0) & \multicolumn{ 5}{c|}{18} & 3 & 2,19\% & 85,71\% & 2,88\% \\ \hline
middle-middle-square = x AND
bottom-right-square = b AND
top-left-square = o AND
top-middle-square = x: positive (18.0/3.0) & \multicolumn{ 5}{c|}{18} & 3 & 2,19\% & 85,71\% & 2,88\% \\ \hline
bottom-right-square = x AND
middle-middle-square = b AND
top-left-square = b: positive (20.0) & \multicolumn{ 5}{c|}{20} & 0 & 2,09\% & 100,00\% & 3,19\% \\ \hline
middle-middle-square = x AND
top-right-square = b AND
bottom-left-square = x: positive (14.0) & \multicolumn{ 5}{c|}{14} & 0 & 1,46\% & 100,00\% & 2,24\% \\ \hline
top-left-square = x AND
middle-right-square = b AND
bottom-middle-square = o AND
top-middle-square = x: positive (16.0/3.0) & \multicolumn{ 5}{c|}{16} & 3 & 1,98\% & 84,21\% & 2,56\% \\ \hline
bottom-right-square = x AND
top-middle-square = b AND
middle-left-square = o AND
middle-right-square = x: positive (16.0/3.0) & \multicolumn{ 5}{c|}{16} & 3 & 1,98\% & 84,21\% & 2,56\% \\ \hline
top-left-square = x AND
bottom-middle-square = b AND
middle-right-square = b: positive (16.0) & \multicolumn{ 5}{c|}{16} & 0 & 1,67\% & 100,00\% & 2,56\% \\ \hline
top-middle-square = b AND
middle-left-square = x AND
bottom-right-square = x: positive (15.0) & \multicolumn{ 5}{c|}{15} & 0 & 1,57\% & 100,00\% & 2,40\% \\ \hline
bottom-middle-square = x AND
middle-right-square = b AND
top-left-square = x: positive (15.0) & \multicolumn{ 5}{c|}{15} & 0 & 1,57\% & 100,00\% & 2,40\% \\ \hline
middle-left-square = b AND
top-right-square = x AND
bottom-middle-square = b: positive (12.0) & \multicolumn{ 5}{c|}{12} & 0 & 1,25\% & 100,00\% & 1,92\% \\ \hline
top-middle-square = b AND
middle-right-square = x: positive (28.0/5.0) & \multicolumn{ 5}{c|}{28} & 5 & 3,44\% & 84,85\% & 4,47\% \\ \hline
top-right-square = b AND
middle-left-square = x AND
bottom-left-square = x: positive (17.0) & \multicolumn{ 5}{c|}{17} & 0 & 1,77\% & 100,00\% & 2,72\% \\ \hline
top-right-square = x AND
middle-right-square = x AND
bottom-right-square = x: positive (27.0) & \multicolumn{ 5}{c|}{27} & 0 & 2,82\% & 100,00\% & 4,31\% \\ \hline
middle-left-square = b AND
bottom-middle-square = x AND
top-right-square = o AND
bottom-right-square = x: positive (16.0/3.0) & \multicolumn{ 5}{c|}{16} & 3 & 1,98\% & 84,21\% & 2,56\% \\ \hline
middle-left-square = o AND
middle-middle-square = o AND
middle-right-square = o: negative (35.0) & \multicolumn{ 5}{c|}{35} & 0 & 3,65\% & 100,00\% & 5,59\% \\ \hline
middle-middle-square = o AND
top-middle-square = b: positive (9.0) & \multicolumn{ 5}{c|}{9} & 0 & 0,94\% & 100,00\% & 1,44\% \\ \hline
top-right-square = b AND
bottom-left-square = x: positive (12.0) & \multicolumn{ 5}{c|}{12} & 0 & 1,25\% & 100,00\% & 1,92\% \\ \hline
top-left-square = b AND
bottom-right-square = x: positive (12.0) & \multicolumn{ 5}{c|}{12} & 0 & 1,25\% & 100,00\% & 1,92\% \\ \hline
top-middle-square = b AND
bottom-right-square = o: negative (14.0/1.0) & \multicolumn{ 5}{c|}{14} & 1 & 1,57\% & 93,33\% & 2,24\% \\ \hline
top-left-square = o AND
bottom-right-square = b AND
top-right-square = o: negative (11.0) & \multicolumn{ 5}{c|}{11} & 0 & 1,15\% & 100,00\% & 1,76\% \\ \hline
bottom-right-square = b: positive (25.0) & \multicolumn{ 5}{c|}{25} & 0 & 2,61\% & 100,00\% & 3,99\% \\ \hline
top-middle-square = o AND
top-left-square = o AND
top-right-square = o: negative (20.0) & \multicolumn{ 5}{c|}{20} & 0 & 2,09\% & 100,00\% & 3,19\% \\ \hline
bottom-left-square = b AND
top-right-square = x: positive (12.0) & \multicolumn{ 5}{c|}{12} & 0 & 1,25\% & 100,00\% & 1,92\% \\ \hline
middle-right-square = x AND middle-left-square = x: positive (15.0/2.0) & \multicolumn{ 5}{c|}{15} & 2 & 1,77\% & 88,24\% & 2,40\% \\ \hline
\textit{middle-right-square = b: positive (14.0)} & \multicolumn{ 5}{c|}{14} & 0 & 1,46\% & 100,00\% & 2,24\% \\ \hline
middle-left-square = b: positive (6.0) & \multicolumn{ 5}{c|}{6} & 0 & 0,63\% & 100,00\% & 0,96\% \\ \hline
middle-middle-square = x AND
top-middle-square = x AND
bottom-middle-square = x: positive (7.0) & \multicolumn{ 5}{c|}{7} & 0 & 0,73\% & 100,00\% & 1,12\% \\ \hline
top-left-square = x AND
middle-right-square = o: positive (11.0/2.0) & \multicolumn{ 5}{c|}{11} & 2 & 1,36\% & 84,62\% & 1,76\% \\ \hline
top-left-square = x AND
top-right-square = x: positive (3.0/1.0) & \multicolumn{ 5}{c|}{3} & 1 & 0,42\% & 75,00\% & 0,48\% \\ \hline
bottom-right-square = x: positive (4.0/1.0) & \multicolumn{ 5}{c|}{4} & 1 & 0,52\% & 80,00\% & 0,64\% \\ \hline
top-left-square = o AND
top-right-square = x: negative (3.0/1.0) & \multicolumn{ 5}{c|}{1} & 3 & 0,42\% & 75,00\% & 0,48\% \\ \hline
middle-middle-square = x: negative (12.0) & \multicolumn{ 5}{c|}{0} & 12 & 1,25\% & 100,00\% & 1,92\% \\ \hline
middle-left-square = x AND
bottom-left-square = b: negative (6.0) & \multicolumn{ 5}{c|}{0} & 6 & 0,63\% & 100,00\% & 0,96\% \\ \hline
middle-left-square = o AND
bottom-left-square = o AND
top-left-square = o: negative (17.0) & \multicolumn{ 5}{c|}{0} & 17 & 1,77\% & 100,00\% & 2,72\% \\ \hline
middle-left-square = b AND
top-right-square = o AND
middle-right-square = o: negative (6.0) & \multicolumn{ 5}{c|}{0} & 6 & 0,63\% & 100,00\% & 0,96\% \\ \hline
bottom-middle-square = o AND
bottom-left-square = o AND
bottom-right-square = o: negative (11.0) & \multicolumn{ 5}{c|}{0} & 11 & 1,15\% & 100,00\% & 1,76\% \\ \hline
bottom-middle-square = o AND
top-middle-square = o AND
middle-middle-square = o: negative (35.0) & \multicolumn{ 5}{c|}{0} & 35 & 3,65\% & 100,00\% & 5,59\% \\ \hline
top-right-square = o AND
middle-middle-square = b AND
bottom-left-square = x AND
bottom-right-square = o: negative (9.0/1.0) & \multicolumn{ 5}{c|}{1} & 9 & 1,04\% & 90,00\% & 1,44\% \\ \hline
bottom-right-square = o AND
top-left-square = o AND
middle-middle-square = o: negative (50.0) & \multicolumn{ 5}{c|}{0} & 50 & 5,22\% & 100,00\% & 7,99\% \\ \hline
\end{longtable}


\paragraph{Evaluación del modelo}

\begin{itemize}
\item Tiempo de ejecución: 0.11 segundos.
\item Accuracy : 905(94.4676 %)
\item Kappa statistic: 0.8772.
\item Mean absolute error: 0.0647.
\item Root mean squared error: 0.218.
\item Relative absolute error: 14.2891 %.
\item Root relative squared error: 45.8131 %.
\end{itemize}

\pagebreak
\section{Conclusiones}

La principal diferencia ente ID3 y C4.5 es el tamaño del árbol. C4.5 realiza una post-poda los árboles consiguiendo, entonces, árboles más pequeños que en el caso de ID3.  

C4.5 realiza simplificaciones para poder obtener árboles más pequeños.  ID3 no generaliza resultados, esto es, no permite que una hoja cubra casos de una clase distinta a la expresada, como sí ocurre con C4.5. Si bien, C4.5 no cubre exhaustivamente todos los casos, permite obtener árboles más pequeños, sin sacrificar precisión. Esta característica de ID3 podría llevar a un sobreajuste, por su necesidad de cubrir absolutamente todos los casos.

Finalmente, dado que el árbol obtenido con C4.5 es más simple, permite obtener reglas más claras y que presenten mayor calidad que las que se obtienen con ID3. La necesidad de explorar absolutamente todos los casos posibles en ID3 hace que se obtengan reglas con bajo nivel de Soporte y Captura, pero gran nivel de Confianza. No podemos decir, sin embargo, que en el caso de C4.5 se obtienen mejores resultados, porque no se obtuvieron reglas con alto grado de soporte y confianza. Esto puede deberse a las características de la base de datos.

Asimismo, debido a que C4.5 hace una poda del árbol y no explora todos los casos posibles, podemos decir que es un algoritmo más rápido que ID3.

Concluimos entonces que la performance es mejor en C4.5, pero requiere una mayor complejidad de implementación debido a la necesidad de realizar la poda del árbol. C4.5 permite obtener árboles más compactos, más rápidamente a un costo de implementación un poco mayor que ID3. En relación a las reglas obtenidas, no podemos concluir que un algoritmo sea mejor que el otro. La decisión de qué algoritmo a aplicar dependerá del dominio de aplicación y de las características de la base de datos.







\pagebreak
\begin{thebibliography}{99}





\bibitem{} Sistemas Inteligentes - García Martinez, Pasquini, Editorial Nueva Librería.

\bibitem{} UCI Repository: http://archive.ics.uci.edu/ml/index.html

\bibitem{} WEKA: http://www.cs.waikato.ac.nz/ml/weka/

\bibitem{} RapidMiner http://rapid-i.com/content/view/181/190/

\end{thebibliography}








\end{document}